f = {}
dp = {}
def get_f(n):
if n in f:
return f[n]
if n == 0:
return 1
res = 0
for i in range(0, n):
res += get_f(i) * get_f(n - 1 - i)
f[n] = res
return res
def get_dp(n, h):
if (n, h) in dp:
return dp[n, h]
if h > n:
return 0
if n <= 1:
return 1
res = 0
for i in range(0, n):
res += get_dp(i, h - 1) * get_f(n - i - 1) + \
get_dp(n - i - 1, h - 1) * get_f(i) - \
get_dp(i, h - 1) * get_dp(n - i - 1, h - 1)
dp[n, h] = res
return res
n, h = map(int, input().split())
print(get_dp(n, h))
#include <bits/stdc++.h>
using namespace std;
int main(){
int n, k;
cin >> n >> k;
long long d[n+1][n+1];
memset(d, 0, sizeof(d));
d[0][0] = d[1][1] = 1;
for(int i=2; i <= n; i++){
for(int j=2; j <= n; j++){
for(int o=0; o<i; o++){
long long l=0, r=0;
for(int h=0; h<j; h++){
l += d[o][h], r += d[i-o-1][h];
}
d[i][j] += l * d[i-o-1][j-1] - d[i-o-1][j-1] * d[o][j-1] + r * d[o][j-1];
}
}
}
long long wa=0;
for(int i=k; i <= n; i++) wa += d[n][i];
cout << wa;
return 0;
}
967. Numbers With Same Consecutive Differences | 957. Prison Cells After N Days |
946. Validate Stack Sequences | 921. Minimum Add to Make Parentheses Valid |
881. Boats to Save People | 497. Random Point in Non-overlapping Rectangles |
528. Random Pick with Weight | 470. Implement Rand10() Using Rand7() |
866. Prime Palindrome | 1516A - Tit for Tat |
622. Design Circular Queue | 814. Binary Tree Pruning |
791. Custom Sort String | 787. Cheapest Flights Within K Stops |
779. K-th Symbol in Grammar | 701. Insert into a Binary Search Tree |
429. N-ary Tree Level Order Traversal | 739. Daily Temperatures |
647. Palindromic Substrings | 583. Delete Operation for Two Strings |
518. Coin Change 2 | 516. Longest Palindromic Subsequence |
468. Validate IP Address | 450. Delete Node in a BST |
445. Add Two Numbers II | 442. Find All Duplicates in an Array |
437. Path Sum III | 436. Find Right Interval |
435. Non-overlapping Intervals | 406. Queue Reconstruction by Height |